{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Space Wasted From Packaging"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #prefix-sum #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #前缀和 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minWastedSpace"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #装包裹的最小浪费空间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你 <code>n</code> 个包裹，你需要把它们装在箱子里，<strong>每个箱子装一个包裹</strong>。总共有 <code>m</code> 个供应商提供 <strong>不同尺寸</strong> 的箱子（每个规格都有无数个箱子）。如果一个包裹的尺寸 <strong>小于等于</strong> 一个箱子的尺寸，那么这个包裹就可以放入这个箱子之中。</p>\n",
    "\n",
    "<p>包裹的尺寸用一个整数数组 <code>packages</code> 表示，其中 <code>packages[i]</code> 是第 <code>i</code> 个包裹的尺寸。供应商用二维数组 <code>boxes</code> 表示，其中 <code>boxes[j]</code> 是第 <code>j</code> 个供应商提供的所有箱子尺寸的数组。</p>\n",
    "\n",
    "<p>你想要选择 <strong>一个供应商</strong> 并只使用该供应商提供的箱子，使得 <strong>总浪费空间最小</strong> 。对于每个装了包裹的箱子，我们定义 <strong>浪费的</strong> 空间等于 <code>箱子的尺寸 - 包裹的尺寸</code> 。<strong>总浪费空间</strong> 为 <strong>所有</strong> 箱子中浪费空间的总和。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，如果你想要用尺寸数组为 <code>[4,8]</code> 的箱子装下尺寸为 <code>[2,3,5]</code> 的包裹，你可以将尺寸为 <code>2</code> 和 <code>3</code> 的两个包裹装入两个尺寸为 <code>4</code> 的箱子中，同时把尺寸为 <code>5</code> 的包裹装入尺寸为 <code>8</code> 的箱子中。总浪费空间为 <code>(4-2) + (4-3) + (8-5) = 6</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你选择 <strong>最优</strong> 箱子供应商，使得 <strong>总浪费空间最小</strong> 。如果 <strong>无法</strong> 将所有包裹放入箱子中，请你返回 <code>-1</code> 。由于答案可能会 <strong>很大</strong> ，请返回它对<strong> </strong><code>10<sup>9</sup> + 7</code> <b>取余</b> 的结果。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>packages = [2,3,5], boxes = [[4,8],[2,8]]\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>选择第一个供应商最优，用两个尺寸为 4 的箱子和一个尺寸为 8 的箱子。\n",
    "总浪费空间为 (4-2) + (4-3) + (8-5) = 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>没有箱子能装下尺寸为 5 的包裹。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]\n",
    "<b>输出：</b>9\n",
    "<b>解释：</b>选择第三个供应商最优，用两个尺寸为 5 的箱子，两个尺寸为 10 的箱子和两个尺寸为 14 的箱子。\n",
    "总浪费空间为 (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == packages.length</code></li>\n",
    "\t<li><code>m == boxes.length</code></li>\n",
    "\t<li><code>1 <= n <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= m <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= packages[i] <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= boxes[j].length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= boxes[j][k] <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>sum(boxes[j].length) <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>boxes[j]</code> 中的元素 <strong>互不相同</strong> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-space-wasted-from-packaging](https://leetcode.cn/problems/minimum-space-wasted-from-packaging/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-space-wasted-from-packaging](https://leetcode.cn/problems/minimum-space-wasted-from-packaging/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,5]\\n[[4,8],[2,8]]', '[2,3,5]\\n[[1,4],[2,3],[3,4]]', '[3,5,8,10,11,12]\\n[[12],[11,9],[10,5,14]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        inc_packages = sorted(packages)\n",
    "        ans = float('inf')\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < inc_packages[-1]:\n",
    "                continue\n",
    "            wasted = 0\n",
    "            start_idx = 0\n",
    "            for b in box:\n",
    "                first_larger_idx = bisect_right(inc_packages, b, lo=start_idx)\n",
    "                wasted += (first_larger_idx - start_idx) * b\n",
    "                if wasted > ans:\n",
    "                    break\n",
    "                start_idx = first_larger_idx\n",
    "            ans = min(ans, wasted)\n",
    "        if ans == float('inf'):\n",
    "            return -1\n",
    "        return (ans - sum(packages)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        packages.sort()\n",
    "        ans = float('inf')\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < packages[-1]:\n",
    "                continue\n",
    "            wasted = 0\n",
    "            start_idx = 0\n",
    "            for b in box:\n",
    "                first_larger_idx = bisect_right(packages, b, lo=start_idx)\n",
    "                wasted += (first_larger_idx - start_idx) * b\n",
    "                start_idx = first_larger_idx\n",
    "            ans = min(ans, wasted)\n",
    "        if ans == float('inf'):\n",
    "            return -1\n",
    "        return (ans - sum(packages)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        packages.sort()\n",
    "        tot = sum(packages)\n",
    "        rs=inf\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < packages[-1]: continue\n",
    "            base,rs0=0,0\n",
    "            for b in box:\n",
    "                if b<packages[0]: continue\n",
    "                if b>=packages[-1]:\n",
    "                    rs0+=b*(len(packages)-base)\n",
    "                    break\n",
    "                idx = bisect_right(packages,b)\n",
    "                rs0+=b*(idx-base)\n",
    "                base=idx\n",
    "                if rs0==tot: return 0    \n",
    "                if rs0>rs: break\n",
    "            rs=min(rs0,rs) if rs!=-1 else rs0\n",
    "        return -1 if rs==inf else (rs-tot)%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        packages.sort()\n",
    "        tot = sum(packages)\n",
    "        rs=inf\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < packages[-1]: continue\n",
    "            base,rs0=0,0\n",
    "            for b in box:\n",
    "                if b<packages[0]: continue\n",
    "                if b>=packages[-1]:\n",
    "                    rs0+=b*(len(packages)-base)\n",
    "                    break\n",
    "                idx = bisect_right(packages,b)\n",
    "                rs0+=b*(idx-base)\n",
    "                base=idx\n",
    "                #if rs0==tot: return 0    \n",
    "                #if rs0>rs: break\n",
    "            rs=min(rs0,rs) if rs!=-1 else rs0\n",
    "        return -1 if rs==inf else (rs-tot)%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        packages.sort()\n",
    "        ans = float(\"inf\")\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if packages[-1] > box[-1]:\n",
    "                continue\n",
    "            idx = 0\n",
    "            curr = 0\n",
    "            for b in box:\n",
    "                last = idx\n",
    "                idx = bisect.bisect_right(packages, b, lo=last)\n",
    "                # 我们需要(idx-last)个箱子b\n",
    "                curr += (idx - last) * b\n",
    "            ans = min(ans, curr)\n",
    "        return (ans-sum(packages)) % (10 ** 9 + 7) if ans != float(\"inf\") else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        ans = -1\n",
    "        n,m = len(packages),len(boxes)\n",
    "        packages.sort()\n",
    "        for i in range(m):\n",
    "            boxes[i].sort()\n",
    "        pre = [0]\n",
    "        for c in packages:\n",
    "            pre.append(pre[-1] + c)\n",
    "        for i in range(m):\n",
    "            tmp = 0\n",
    "            lst = 0\n",
    "            for j in boxes[i]:\n",
    "                if lst >= n:\n",
    "                    break\n",
    "                pos = bisect.bisect_right(packages,j) - 1\n",
    "                if pos < 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    # 将lst-pos这段\n",
    "                    tot = pre[pos + 1] - pre[lst]\n",
    "                    tmp += (pos - lst + 1) * j - tot\n",
    "                    \n",
    "                    \n",
    "                    lst = pos + 1\n",
    "                    \n",
    "                    \n",
    "            if lst >= n:\n",
    "                \n",
    "                if ans == -1 or ans > tmp:\n",
    "                    ans = tmp\n",
    "        if ans == -1:\n",
    "            return ans\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        n = len(packages)\n",
    "        packages.sort()\n",
    "        pres = list(accumulate(packages, initial=0))\n",
    "        res = float('inf')\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < packages[-1]:\n",
    "                continue\n",
    "            cur = 0\n",
    "            i = 0\n",
    "            for j, b in enumerate(box):\n",
    "                ni = bisect_right(packages, b)\n",
    "                cur += b * (ni - i) - (pres[ni] - pres[i])\n",
    "                i = ni\n",
    "                if i==n:\n",
    "                    break\n",
    "            res = min(res, cur)\n",
    "\n",
    "        return -1 if res == float('inf') else res% 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages, boxes):\n",
    "        packages.sort()\n",
    "        result = -1\n",
    "        allboxes = []\n",
    "        for supplier in boxes:\n",
    "            allboxes.extend(supplier)\n",
    "        allboxes.sort()\n",
    "        packageindex = {}\n",
    "        totalsize = 0\n",
    "        box_index = 0\n",
    "\n",
    "        for pi, pck in enumerate(packages):\n",
    "            totalsize += pck\n",
    "            while pck > allboxes[box_index]:\n",
    "                packageindex[allboxes[box_index]] = pi - 1\n",
    "                box_index += 1\n",
    "                if box_index >= len(allboxes):\n",
    "                    # no supplier fits\n",
    "                    return -1\n",
    "            # box fits\n",
    "        for i in range(box_index, len(allboxes)):\n",
    "            packageindex[allboxes[i]] = len(packages) - 1\n",
    "        \n",
    "        for supplier in boxes:\n",
    "            supplier.sort()\n",
    "            waste = 0\n",
    "            donepackages = 0\n",
    "            total_box_size = 0\n",
    "            for box in supplier:\n",
    "                topack = packageindex.get(box, -1) + 1\n",
    "                \n",
    "                total_box_size += (topack - donepackages) * box\n",
    "                donepackages = topack\n",
    "            if topack < len(packages):\n",
    "                waste = -1\n",
    "            else:\n",
    "                waste = total_box_size - totalsize\n",
    "            if waste != -1:\n",
    "                if result == -1:\n",
    "                    result = waste\n",
    "                else:\n",
    "                    result = min(result, waste)\n",
    "        if result != -1:\n",
    "            return int(result % (1e9 +7))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        packages.sort()\n",
    "        pre = list(accumulate(packages, initial=0))\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        def calu(box):\n",
    "            s = 0\n",
    "            # box.sort()\n",
    "            # for x in packages:\n",
    "            #     j = bisect_left(box, x)\n",
    "            #     s += box[j] - x\n",
    "            p = 0\n",
    "            for x in box:\n",
    "                j = bisect_right(packages, x)\n",
    "                s += (x * (j-p)) - (pre[j] - pre[p])\n",
    "                p = j\n",
    "            return s\n",
    "    \n",
    "        ans = inf\n",
    "        mx = packages[-1]\n",
    "        # j = bisect_left(large, (mx, -1))\n",
    "        # if j == len(boxes):\n",
    "        #     return -1\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < mx:\n",
    "                continue\n",
    "            ans = min(ans, calu(box))\n",
    "        \n",
    "        return ans % MOD if ans < inf else -1\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        ans = inf\n",
    "        packages.sort()\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(len(boxes)):\n",
    "            boxes[i].sort()\n",
    "\n",
    "        pres = list(accumulate(packages,initial=0))\n",
    "\n",
    "        for box in boxes:\n",
    "            if box[-1] < packages[-1]:continue\n",
    "            l = 0\n",
    "            s = 0\n",
    "            for x in box:\n",
    "                if l >= len(packages):break\n",
    "                r = bisect.bisect_right(packages,x)\n",
    "                s += (r - l) * x - (pres[r] - pres[l])\n",
    "                l = r\n",
    "            ans = min(ans,s)\n",
    "        return ans % mod if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        packages.sort()\n",
    "        total = [0]\n",
    "        for p in packages:\n",
    "            total.append(total[-1] + p)\n",
    "        res = float('inf')\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < packages[-1]:\n",
    "                continue\n",
    "            i, cur = 0, 0\n",
    "            for b in box:\n",
    "                j = bisect.bisect_right(packages, b)\n",
    "                cur += b * (j - i) - (total[j] - total[i])\n",
    "                i = j\n",
    "            res = min(res, cur)\n",
    "        return res % 1000000007 if res != float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "      packages.sort()\n",
    "      pre_sum = [0]\n",
    "      for idx,i in enumerate(packages):\n",
    "        pre_sum.append(pre_sum[-1]+i)\n",
    "      #对boxes内子数组排序\n",
    "      for i in range(len(boxes)):\n",
    "        boxes[i] = sorted(boxes[i])\n",
    "      res = float('inf')\n",
    "      for box in boxes:\n",
    "        cur = 0\n",
    "        l = 0\n",
    "        if box[-1]<packages[-1]:continue\n",
    "        for j in box:\n",
    "          r = bisect.bisect_right(packages,j)\n",
    "          cur += (r-l)*j-(pre_sum[r]-pre_sum[l])\n",
    "          l = r\n",
    "        res = min(res,cur)\n",
    "      return int(res%(10**9+7)) if res != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        pack=sorted(packages)\n",
    "        pre=[0]\n",
    "        for i in packages:\n",
    "            pre.append(i+pre[-1])\n",
    "        res=10**20\n",
    "        for b in boxes:\n",
    "            sb=sorted(b)\n",
    "            if sb[-1]<pack[-1]:\n",
    "                continue\n",
    "            p=-1\n",
    "            ans=0\n",
    "            for bi in sb:\n",
    "                r=bisect_right(pack,bi)\n",
    "                if r-1>p:\n",
    "                    ans+=(r-1-(p+1)+1)*bi-(pre[r]-pre[p+1])\n",
    "                p=r-1\n",
    "            res=min(res,ans)\n",
    "        return res%(10**9+7) if res<10**20 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        n = len(packages)\n",
    "        packages.sort()\n",
    "        pref = [0] + list(accumulate(packages))\n",
    "        MOD = 10**9+7\n",
    "\n",
    "        ans = inf\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < packages[-1]:\n",
    "                continue\n",
    "            pre = 0\n",
    "            res = 0\n",
    "            for b in box:\n",
    "                cur = bisect_right(packages,b) - 1\n",
    "                res = res + b*(cur-pre+1) - (pref[cur+1]-pref[pre])\n",
    "                # print(b,cur,pre,res,pref[cur+1]-pref[pre])\n",
    "                pre = cur + 1\n",
    "                \n",
    "                if pre ==n:\n",
    "                    break\n",
    "            if res<ans:\n",
    "                ans = res\n",
    "        if ans == inf:\n",
    "            return -1\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        packages.sort()\n",
    "        n, m, pre, result, MOD = len(packages), len(boxes), [0] + list(accumulate(packages)), inf, 10 ** 9 + 7\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if packages[-1] <= box[-1]:\n",
    "                cur, last = 0, 0\n",
    "                for b in box:\n",
    "                    pos = bisect.bisect_right(packages, b)\n",
    "                    cur += b * (pos - last) - (pre[pos] - pre[last])\n",
    "                    last = pos\n",
    "                result = min(cur, result)\n",
    "        return result % MOD if result < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        inc_packages = sorted(packages)\n",
    "        presum = [0]\n",
    "        for p in inc_packages:\n",
    "            presum.append(presum[-1] + p)\n",
    "        ans = float('inf')\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < inc_packages[-1]:\n",
    "                continue\n",
    "            wasted = 0\n",
    "            prev_idx = 0\n",
    "            for b in box:\n",
    "                if b < inc_packages[prev_idx]:\n",
    "                    continue\n",
    "                first_larger_idx = bisect_right(inc_packages, b)\n",
    "                wasted += (first_larger_idx - prev_idx) * b - (presum[first_larger_idx] - presum[prev_idx])\n",
    "                prev_idx = first_larger_idx\n",
    "                if prev_idx == len(packages):\n",
    "                    break\n",
    "            ans = min(ans, wasted)\n",
    "        if ans == float('inf'):\n",
    "            return -1\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, A: List[int], B: List[List[int]]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 300 ms ... 84 % ... 37.9 MB ... 0 %\n",
    "        #  time: O(n+m+p*qlogq) ... n=len(A), m=max(A), p=len(B), q=len(B[0])\n",
    "        # space: O(m+q)\n",
    "        \n",
    "        mx = max(A)\n",
    "        f = [0]*(mx+1)            # f[a] 是体积为 a 的包裹的个数\n",
    "        for a in A:\n",
    "            f[a] += 1\n",
    "        c = [0]*(mx+1)            # c[a] 是不超过 a 的包裹总个数\n",
    "        s = [0]*(mx+1)            # s[a] 是不超过 a 的包裹总体积\n",
    "        for a in range(1, mx+1):\n",
    "            c[a] = c[a-1] + f[a]\n",
    "            s[a] = s[a-1] + f[a] * a\n",
    "        minwaste = float('inf')\n",
    "        for b in B:\n",
    "            b, pc, ps, curwaste = sorted(b), 0, 0, 0\n",
    "            if mx <= b[-1]:\n",
    "                for i in range(len(b)):\n",
    "                    cc = c[b[i]] if b[i] <= mx else c[-1]\n",
    "                    cs = s[b[i]] if b[i] <= mx else s[-1]\n",
    "                    curwaste += (cc-pc)*b[i] - (cs-ps)\n",
    "                    pc, ps = cc, cs\n",
    "                minwaste = min(minwaste, curwaste)\n",
    "        return -1 if minwaste == float('inf') else minwaste % (10**9 + 7)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        ma, mod = max(packages), 10 ** 9 + 7\n",
    "        preCnt, preSum = [0] * 100010, [0] * 100010\n",
    "        for p in packages:\n",
    "            preCnt[p] += 1\n",
    "            preSum[p] += p\n",
    "        for i in range(1, 100010):\n",
    "            preCnt[i] += preCnt[i - 1]\n",
    "            preSum[i] += preSum[i - 1]\n",
    "\n",
    "        def check(box):\n",
    "            box.sort()\n",
    "            if box[-1] < ma:\n",
    "                return float(\"inf\")\n",
    "            res = pre = 0\n",
    "            for b in box:\n",
    "                res += (preCnt[b] - preCnt[pre]) * b - (preSum[b] - preSum[pre])\n",
    "                pre = b\n",
    "            return res\n",
    "            \n",
    "        res = float(\"inf\")\n",
    "        for box in boxes:\n",
    "            res = min(res, check(box))\n",
    "        return res % mod if res != float(\"inf\") else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        mod = 10**9+7\n",
    "        A = sorted(packages)\n",
    "        pre = list(accumulate([0]+A))\n",
    "        res = inf\n",
    "        for B in boxes:\n",
    "            B.sort()\n",
    "            if B[-1]<A[-1]:\n",
    "                continue\n",
    "            tmp,i = 0,0\n",
    "            for x in B:\n",
    "                j = bisect_right(A,x)\n",
    "                tmp += (j-i)*x-(pre[j]-pre[i])\n",
    "                i = j\n",
    "            res = min(res, tmp)\n",
    "        return res%mod if res<inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        # 差分+前缀和\n",
    "        packages.sort()\n",
    "        max_len = 0\n",
    "        for i in boxes:\n",
    "            i.sort()\n",
    "            max_len = max(max_len,i[-1])\n",
    "        if packages[-1] > max_len:\n",
    "            return -1\n",
    "        packages_sum = [0]*(len(packages)+1)\n",
    "        for i in range(len(packages)):\n",
    "            packages_sum[i+1] = packages[i] + packages_sum[i]\n",
    "        S = [0]*(max_len+1)\n",
    "        for i in packages:\n",
    "            S[i] += 1\n",
    "        SS = [0]*(max_len+2)\n",
    "        for i in range(1,max_len+1):\n",
    "            SS[i+1] = SS[i] + S[i]\n",
    "        res = 10**18\n",
    "        for box in boxes:\n",
    "            if box[-1] < packages[-1]:\n",
    "                continue\n",
    "            pre = 0\n",
    "            count = 0\n",
    "            for i in box:\n",
    "                count += (SS[i+1] - pre) * i - (packages_sum[SS[i+1]] - packages_sum[pre])\n",
    "                pre = SS[i+1]\n",
    "            res = min(res,count)\n",
    "        return res%(10**9+7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        n = len(packages)\n",
    "        m = len(boxes)\n",
    "        packages.sort()\n",
    "        presum = [0]\n",
    "        for i in range(n):\n",
    "            presum.append(presum[-1] + packages[i])\n",
    "        ans = float('inf')\n",
    "        for vs in boxes:\n",
    "            vs.sort(reverse=True)\n",
    "            if vs[0] < packages[-1]:\n",
    "                continue\n",
    "            d = {}\n",
    "            for v in vs:\n",
    "                idx = bisect.bisect_right(packages, v)\n",
    "                d[idx] = v\n",
    "                if idx == 0:\n",
    "                    break\n",
    "            d = sorted(d.items())\n",
    "            res = 0\n",
    "            idx2 = 0\n",
    "            for idx, v in d:\n",
    "                res += v * (idx - idx2) - (presum[idx] - presum[idx2])\n",
    "                idx2 = idx\n",
    "            ans = min(ans, res)\n",
    "        return ans % 1000000007 if ans < float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        res = float('inf')\n",
    "        n = len(packages)\n",
    "        m = len(boxes)\n",
    "        \n",
    "        ps = sorted(packages)\n",
    "        prefix = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            prefix[i+1] = prefix[i] + ps[i]\n",
    "        \n",
    "        wastes = [0] * m\n",
    "        for i in range(m):\n",
    "            done = False\n",
    "            boxes[i] = sorted(boxes[i])\n",
    "            pre = 0\n",
    "            for j in range(len(boxes[i])):\n",
    "                b = boxes[i][j]\n",
    "                k = bisect.bisect_right(ps, b)\n",
    "                wastes[i] += b * (k-pre) - (prefix[k] - prefix[pre])\n",
    "                pre = k\n",
    "                if k >= n:\n",
    "                    done = True\n",
    "                    break\n",
    "            if done:\n",
    "                res = min(res, wastes[i])\n",
    "        \n",
    "        if res == float('inf'):\n",
    "            return -1\n",
    "        return res % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "#         packages.sort()\n",
    "#         rst = float(\"inf\")\n",
    "#         n = len(packages)\n",
    "#         for box in boxes:\n",
    "#             box.sort()\n",
    "#             if box[-1] < packages[-1]:\n",
    "#                 continue\n",
    "\n",
    "#             i = 0\n",
    "#             s = 0\n",
    "#             cur_old = 0\n",
    "#             while cur_old < len(packages):\n",
    "#                 cur_new = bisect.bisect_right(packages, box[i])\n",
    "#                 s += (cur_new - cur_old) * box[i]\n",
    "#                 cur_old = cur_new\n",
    "#                 i += 1\n",
    "#             rst = min(rst, s)\n",
    "#         if rst == float(\"inf\"):\n",
    "#             return -1\n",
    "#         return (rst - sum(packages)) % (10 ** 9 + 7)\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        packages.sort()\n",
    "        rst = float(\"inf\")\n",
    "        n = len(packages)\n",
    "        boxes = [sorted(box) for box in boxes if max(box) >= packages[-1]]\n",
    "        if not boxes:\n",
    "            return -1\n",
    "        M = max(max(box) for box in boxes)\n",
    "        box_con = [0] * (M + 1)\n",
    "        for i, p in enumerate(packages):\n",
    "            box_con[p] = i\n",
    "        box_con[-1] = n - 1\n",
    "        for i in range(1, M + 1):\n",
    "            if box_con[i] == 0:\n",
    "                box_con[i] = box_con[i - 1]\n",
    "        for i in range(packages[0]):\n",
    "            box_con[i] = -1\n",
    "        \n",
    "        for box in boxes:\n",
    "            s = 0\n",
    "            box_use = [-1] + [box_con[b] for b in box]\n",
    "            for i in range(len(box_use) - 1):\n",
    "                s += (box_use[i + 1]- box_use[i]) * box[i]\n",
    "            rst = min(s, rst)\n",
    "\n",
    "        if rst == float(\"inf\"):\n",
    "            return -1\n",
    "        return (rst - sum(packages)) % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        packages.sort()\n",
    "        res, s, dic, lp = float(\"inf\"), [0], {}, len(packages)\n",
    "        for x in packages:\n",
    "            s.append(s[-1] + x)\n",
    "        for x in boxes:\n",
    "            x.sort()\n",
    "            if x[-1] >= packages[-1]:\n",
    "                pp, px, rpre, lx = 0, 0, 0, len(x)\n",
    "                while pp < lp:\n",
    "                    if x[px] in dic:\n",
    "                        rpre += (dic[x[px]] - pp) * x[px] - (s[dic[x[px]]] - s[pp])\n",
    "                        pp = dic[x[px]]\n",
    "                        px += 1\n",
    "                    else:\n",
    "                        left, right = pp, lp\n",
    "                        while left < right:\n",
    "                            mid = (left + right) // 2\n",
    "                            if packages[mid] <= x[px]:\n",
    "                                left = mid + 1\n",
    "                            else:\n",
    "                                right = mid\n",
    "                        rpre += x[px] * (left - pp) - (s[left] - s[pp])\n",
    "                        dic[x[px]], pp = left, left\n",
    "                        px += 1\n",
    "                res = min(res, rpre)\n",
    "        return res % (10 ** 9 + 7) if res != float(\"inf\") else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        MOD = 10**9+7\n",
    "        boxes = [sorted(box) for box in boxes]\n",
    "        packages.sort()\n",
    "        pre_sum = list(accumulate(packages, initial=0))\n",
    "        mx = packages[-1]\n",
    "        ans = inf                  \n",
    "        for box in boxes:\n",
    "            last = 0\n",
    "            res = 0\n",
    "            if(box[-1] < mx):\n",
    "                continue\n",
    "            for b in box:\n",
    "                idx = bisect_right(packages, b)\n",
    "                if(idx > last):\n",
    "                    res += b*(idx-last) - (pre_sum[idx]-pre_sum[last])\n",
    "                    last = idx\n",
    "            if(res < ans):\n",
    "                ans = res\n",
    "        return ans%MOD if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        mod = 10**9+7\n",
    "        n = len(packages)\n",
    "        packages.sort()\n",
    "        boxes = [sorted(b) for b in boxes]\n",
    "        boxes.sort()\n",
    "        \n",
    "        presum = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            presum[i+1] = presum[i]+packages[i]\n",
    "       \n",
    "        #print(presum)\n",
    "        #print(boxes)\n",
    "        res = float('inf')\n",
    "        for box in boxes:\n",
    "            waste = 0\n",
    "            pre_idx = 0\n",
    "            count = 0\n",
    "            for b in box:\n",
    "               \n",
    "                idx = bisect.bisect_right(packages,b)\n",
    "                \n",
    "                if idx==0:\n",
    "                    continue\n",
    "                waste = waste + b*(idx-pre_idx)-(presum[idx]-presum[pre_idx])\n",
    "                \n",
    "                count += idx-pre_idx\n",
    "                pre_idx = idx\n",
    "                \n",
    "                if count==n:\n",
    "                    res = min(res,waste)\n",
    "                else:\n",
    "                    continue\n",
    "        return res%mod if res!=float('inf') else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        n, m = len(packages), len(boxes)\n",
    "        M = 10**9 + 7\n",
    "        packages.sort()\n",
    "        mx = packages[-1]\n",
    "        c = [0] * (mx+1)\n",
    "        for x in packages:\n",
    "            c[x] += 1\n",
    "        for x in range(1,mx+1):\n",
    "            c[x] += c[x-1]\n",
    "        pre = list(itertools.accumulate(packages, initial=0))\n",
    "        \n",
    "        ans = math.inf\n",
    "        for b in boxes:\n",
    "            b.sort()\n",
    "            if b[-1] < mx: continue\n",
    "            waste = 0\n",
    "            x0 = p = 0\n",
    "            for i,x in enumerate(b):\n",
    "                q = c[x] if x <= mx else n\n",
    "                waste += x*(q-p) - (pre[q]-pre[p])\n",
    "                x0,p = x,q\n",
    "            ans = min(ans, waste)\n",
    "        \n",
    "        return ans%M if ans < math.inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        m = len(boxes)\n",
    "        sumPackages = sum(packages)\n",
    "        packages.sort()\n",
    "        totals = [0]*m\n",
    "        pkgIndices = [-1]*m\n",
    "        iterP = iter(packages)\n",
    "        h = [(next(iterP), -1, iterP)]\n",
    "        for bi, bs in enumerate(boxes):\n",
    "            bs.sort()\n",
    "            iterB = iter(bs)\n",
    "            h.append((next(iterB), bi, iterB))\n",
    "        heapify(h)\n",
    "        inf = float('inf')\n",
    "        lastP = -1\n",
    "        while h:\n",
    "            v, idx, it = heappop(h)\n",
    "            nv = next(it, inf)\n",
    "            if idx < 0:\n",
    "                lastP += 1\n",
    "            elif pkgIndices[idx] < lastP:\n",
    "                totals[idx] += (lastP - pkgIndices[idx])*v\n",
    "                pkgIndices[idx] = lastP\n",
    "            if nv == inf: continue\n",
    "            heappush(h, (nv, idx, it))\n",
    "        NP = len(packages)\n",
    "        if lastP != NP - 1: return -1\n",
    "        minWasted = inf\n",
    "        for t, pi in zip(totals, pkgIndices):\n",
    "            if pi < NP - 1: continue\n",
    "            minWasted = min(minWasted, t - sumPackages)\n",
    "        return minWasted % 1000000007 if minWasted != inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        prefix = [0 for i in range(10 ** 5 + 1)]\n",
    "        size = [0 for i in range(10 ** 5 + 1)]\n",
    "        mode = 10 ** 9 + 7\n",
    "        inf = 10 ** 20\n",
    "        for i in packages:\n",
    "            prefix[i] += 1\n",
    "            size[i] += i\n",
    "        for i in range(1, len(prefix)):\n",
    "            prefix[i] += prefix[i - 1]\n",
    "            size[i] += size[i - 1]\n",
    "        for box in boxes:\n",
    "            box.sort(key=lambda x: -x)\n",
    "        max_p = max(packages)\n",
    "        boxes = [box for box in boxes if box[0] >= max_p]\n",
    "        if len(boxes) == 0:\n",
    "            return -1\n",
    "        res = inf\n",
    "        for box in boxes:\n",
    "            tr = 0\n",
    "            ids = 0\n",
    "            for ids in range(1, len(box)):\n",
    "                tr += (prefix[box[ids - 1]] - prefix[box[ids]]) * box[ids - 1] - (size[box[ids - 1]] - size[box[ids]])\n",
    "            tr += (prefix[box[ids]] - prefix[0]) * box[ids] - (size[box[ids]] - size[0])\n",
    "            res = min(res, tr)\n",
    "        return res % mode\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "import operator\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        n = len(packages)\n",
    "        packages = sorted(packages)\n",
    "        boxes = list(sorted(b) for b in boxes)\n",
    "        cum_sum = [0] + list(itertools.accumulate(packages, operator.add))\n",
    "\n",
    "        def find_package_limit(left, right, target):\n",
    "            while left < right and left < n:\n",
    "                mid = (left + right) >> 1\n",
    "                if packages[mid] <= target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return right\n",
    "\n",
    "        ans = -1\n",
    "        for b in boxes:\n",
    "            if packages[-1] > b[-1]:\n",
    "                continue\n",
    "            cur_waste = 0\n",
    "            idx = 0\n",
    "            for size in b:\n",
    "                if idx == n or size < packages[idx]:\n",
    "                    continue\n",
    "                next_idx = find_package_limit(idx, n, size)\n",
    "                total_box_size = (next_idx - idx) * size\n",
    "                total_package_size = cum_sum[next_idx] - cum_sum[idx]\n",
    "                cur_waste += total_box_size - total_package_size\n",
    "                idx = next_idx\n",
    "            if ans == -1 or cur_waste < ans:\n",
    "                ans = cur_waste\n",
    "        if ans == -1:\n",
    "            return -1\n",
    "        return ans % MOD\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        packages.sort()\n",
    "        total = sum(packages)\n",
    "        all_box = set()\n",
    "        for box in boxes:\n",
    "            for num in box:\n",
    "                all_box.add(num)\n",
    "        tar = sorted(list(all_box))\n",
    "        if tar[-1] < packages[-1]:\n",
    "            return -1\n",
    "        import collections\n",
    "        memo = collections.defaultdict(int)\n",
    "        l = 0\n",
    "        r = 0\n",
    "        while l < len(packages):\n",
    "            if packages[l] > tar[r]:\n",
    "                memo[tar[r]] = l\n",
    "                r += 1\n",
    "            else:\n",
    "                l += 1\n",
    "        for other in range(r,len(tar)):\n",
    "            memo[tar[other]] = len(packages)\n",
    "        ans = float('inf')\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < packages[-1]:\n",
    "                continue\n",
    "            temp = 0\n",
    "            cnted = 0\n",
    "            for num in box:\n",
    "                temp += num * (memo[num] - cnted)\n",
    "                cnted = memo[num]\n",
    "            ans = min(ans, temp)\n",
    "        return (ans - total) % (10 ** 9 +7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        packages.sort()\n",
    "        for vendor in boxes:\n",
    "            vendor.sort()\n",
    "\n",
    "        packageIndex = []\n",
    "        for vendor in boxes:\n",
    "            pi = []\n",
    "            for b in vendor:\n",
    "                i = bisect.bisect_right(packages, b)\n",
    "                pi.append(i)\n",
    "            packageIndex.append(pi)\n",
    "\n",
    "        presum = [0]\n",
    "        for v in packages:\n",
    "            presum.append(presum[-1] + v)\n",
    "\n",
    "        ans = float('inf')\n",
    "        for vi, vendor in enumerate(boxes):\n",
    "            waste = 0\n",
    "            preIndex = 0\n",
    "            for bi, b in enumerate(vendor):\n",
    "                i = packageIndex[vi][bi]\n",
    "                waste += (i - preIndex) * b - (presum[i] - presum[preIndex])\n",
    "                preIndex = i\n",
    "            if preIndex >= len(packages):\n",
    "                ans = min(ans, waste)\n",
    "\n",
    "        return ans % (10 ** 9 + 7) if ans < float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: list[int], boxes: list[list[int]]) -> int:\n",
    "        sd = SortedDict()\n",
    "        sd[0] = 0\n",
    "        packages.sort()\n",
    "        mx = packages[-1]\n",
    "        tot = sum(packages)\n",
    "        for p in packages:\n",
    "            sd[p] = 1 + sd.values()[-1]\n",
    "\n",
    "        def f(box):\n",
    "            box.sort()\n",
    "            if box[-1] < mx:\n",
    "                return inf\n",
    "            prev = 0\n",
    "            cnt = 0\n",
    "            for b in box:\n",
    "                i = sd.bisect_right(b)\n",
    "                cur = sd.values()[i - 1] - prev\n",
    "                cnt += b * cur\n",
    "                prev += cur\n",
    "            return (cnt - tot)\n",
    "\n",
    "        a = min(f(box) for box in boxes)\n",
    "        if a == inf:\n",
    "            return -1 \n",
    "        return a % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        INF = 10 ** 12\n",
    "        packages.sort()\n",
    "        boxSet = set()\n",
    "        for b in boxes:\n",
    "            for s in b:\n",
    "                boxSet.add(s)\n",
    "        box = list(boxSet)\n",
    "        box.sort()\n",
    "        ptL = -1; ptR = 0\n",
    "        LP = len(packages); LB = len(box)\n",
    "        smallCnt = {}\n",
    "        if packages[-1] > box[-1]: return -1\n",
    "        while ptL < LP and ptR < LB:\n",
    "            while ptL + 1 < LP and packages[ptL+1] <= box[ptR]:\n",
    "                ptL += 1\n",
    "            smallCnt[box[ptR]] = ptL + 1\n",
    "            ptR += 1\n",
    "        while ptR < LB:\n",
    "            smallCnt[box[ptR]] = LP\n",
    "            ptR += 1\n",
    "        minTotal = INF\n",
    "        # print(smallCnt)\n",
    "        for i in range(len(boxes)):\n",
    "            box = boxes[i]\n",
    "            box.sort()\n",
    "            if box[-1] < packages[-1]: continue\n",
    "            B = len(box)\n",
    "            total = 0\n",
    "            for j in range(B):\n",
    "                total += box[j] * (smallCnt[box[j]])\n",
    "                if j >= 1:\n",
    "                    total -= box[j] * (smallCnt[box[j-1]])\n",
    "            minTotal = min(total, minTotal)\n",
    "        if minTotal == INF:\n",
    "            return -1\n",
    "        else:\n",
    "            MOD = 10 ** 9 + 7\n",
    "            return (minTotal - sum(packages)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        mx = max(packages) + 1\n",
    "        has, hasv = [0] * mx, [0] * mx\n",
    "        for i in packages:\n",
    "            has[i] += 1\n",
    "            hasv[i] += i\n",
    "        pre, prev = [0] * mx, [0] * mx\n",
    "        for i in range(mx):\n",
    "            pre[i] = has[i] + pre[i-1]\n",
    "            prev[i] = hasv[i] + prev[i-1]\n",
    "        res = float('inf')\n",
    "        for lis in boxes:\n",
    "            last, tep = 0, 0\n",
    "            lis = sorted(lis)\n",
    "            if lis[-1] < mx - 1: continue\n",
    "            for v in lis:\n",
    "                if v >= mx:\n",
    "                    tep += (pre[-1] - pre[last]) * v - prev[-1] + prev[last]\n",
    "                    break\n",
    "                tep += (pre[v] - pre[last]) * v - prev[v] + prev[last]\n",
    "                last = v\n",
    "            res = min(res, tep)\n",
    "        return res % 1000000007 if res != float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        \n",
    "        n = len(packages)\n",
    "        m = len(boxes)    \n",
    "        \n",
    "        packages.sort()\n",
    "        \n",
    "        sizes = set()\n",
    "        for i, box in enumerate(boxes):\n",
    "            box.sort()\n",
    "            for x in box:\n",
    "                sizes.add(x)\n",
    "        sizes = sorted(sizes)\n",
    "        \n",
    "        results = {}\n",
    "        for x in sizes:\n",
    "            lb, hb = 0, n\n",
    "            while lb < hb:\n",
    "                mid = lb + (hb - lb) // 2\n",
    "                if packages[mid] <= x:\n",
    "                    lb = mid + 1\n",
    "                else:\n",
    "                    hb = mid\n",
    "            results[x] = lb\n",
    "        \n",
    "        prefix = [0]\n",
    "        for x in packages:\n",
    "            prefix.append(prefix[-1] + x)\n",
    "        \n",
    "        if sizes[-1] < packages[-1]:\n",
    "            return -1\n",
    "        \n",
    "        res = sizes[-1] * n - prefix[-1]\n",
    "        \n",
    "        for box in boxes:\n",
    "            if box[-1] < packages[-1]:\n",
    "                continue\n",
    "            prev = space = 0\n",
    "            for x in box:\n",
    "                j = results[x]\n",
    "                space += (j - prev) * x - (prefix[j] - prefix[prev])\n",
    "                prev = j\n",
    "            res = min(res, space)\n",
    "        \n",
    "        return res % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, p: List[int], boxes: List[List[int]]) -> int:\n",
    "        N = len(p)\n",
    "        d = [0] * 100005\n",
    "        v = [0] * 100005\n",
    "        pp = [0] + list(accumulate(p))\n",
    "        \n",
    "        p.sort()\n",
    "        j = 0\n",
    "        for i in range(1, 100005):\n",
    "            d[i] = d[i-1] + v[i-1]\n",
    "            v[i] = v[i-1]\n",
    "            while j < N and i >= p[j]:\n",
    "                d[i] += i - p[j]\n",
    "                j += 1\n",
    "                v[i] = j\n",
    "        # print(d[:20], v[:20])\n",
    "        \n",
    "        ret = 10 ** 11\n",
    "        for bb in boxes:\n",
    "            bb.sort()\n",
    "            if bb[-1] < p[-1]:\n",
    "                continue\n",
    "            pd, pv = 0, 0\n",
    "            su = 0\n",
    "            for i in bb:\n",
    "                if v[i] == pv:\n",
    "                    continue\n",
    "                # print(bb,i,v[i],su,pv, pp[v[i]] - pp[pv])\n",
    "                su += i * (v[i] - pv) - (pp[v[i]] - pp[pv])                    \n",
    "\n",
    "                pv = v[i]\n",
    "                if i >= p[-1]:\n",
    "                    ret = min(ret, su)\n",
    "                    break            \n",
    "            \n",
    "        if ret == 10 ** 11:\n",
    "            return -1\n",
    "        else:\n",
    "            return ret % (10 ** 9 + 7)\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        \n",
    "        n = len(packages)\n",
    "        \n",
    "        packages.sort()\n",
    "        prefix = [0]\n",
    "        for x in packages:\n",
    "            prefix.append(prefix[-1] + x)\n",
    "        \n",
    "        sizes = set()\n",
    "        for i, box in enumerate(boxes):\n",
    "            box.sort()\n",
    "            for x in box:\n",
    "                sizes.add(x)\n",
    "        sizes = sorted(sizes)\n",
    "\n",
    "        if sizes[-1] < packages[-1]:\n",
    "            return -1\n",
    "        \n",
    "        results = {}\n",
    "        for x in sizes:\n",
    "            lb, hb = 0, n\n",
    "            while lb < hb:\n",
    "                mid = lb + (hb - lb) // 2\n",
    "                if packages[mid] <= x:\n",
    "                    lb = mid + 1\n",
    "                else:\n",
    "                    hb = mid\n",
    "            results[x] = lb\n",
    "        \n",
    "        res = sizes[-1] * n - prefix[-1]\n",
    "        \n",
    "        for box in boxes:\n",
    "            if box[-1] < packages[-1]:\n",
    "                continue\n",
    "            prev = space = 0\n",
    "            for x in box:\n",
    "                j = results[x]\n",
    "                space += (j - prev) * x - (prefix[j] - prefix[prev])\n",
    "                prev = j\n",
    "            res = min(res, space)\n",
    "        \n",
    "        return res % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        max_p = max(packages)\n",
    "        boxes = [sorted(box, reverse=True) for box in boxes if max(box) >= max_p]\n",
    "        if len(boxes) == 0: return -1\n",
    "        max_s = max(map(max, boxes))\n",
    "        \n",
    "        cnt_le = [0 for _ in range(max_s+1)]\n",
    "        # wasted[i]: wasted space if packed all package with size le than i into box size i\n",
    "        wasted = [0 for _ in range(max_s+1)]\n",
    "        for p in packages:\n",
    "            cnt_le[p] += 1\n",
    "        for i in range(1, max_s+1):\n",
    "            cnt_le[i] += cnt_le[i-1]\n",
    "            wasted[i] = wasted[i-1] + cnt_le[i-1]\n",
    "            \n",
    "        # print(cnt_le)\n",
    "        # print(wasted)\n",
    "        \n",
    "        \n",
    "        min_w = float('inf')\n",
    "        for box in boxes:\n",
    "            # print(box)\n",
    "            \n",
    "            last_contained = len(packages)\n",
    "            w = wasted[box[0]]\n",
    "            last_b = box[0]\n",
    "            \n",
    "            for b in box:\n",
    "                contained = cnt_le[b]\n",
    "                w -= contained * (last_b - b)\n",
    "                \n",
    "                last_b = b\n",
    "                last_contained = cnt_le[b]\n",
    "                \n",
    "            min_w = min(w, min_w)\n",
    "        return min_w %(10**9+7) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        ct=Counter(packages)\n",
    "        sct=list(ct)\n",
    "        sct.sort()\n",
    "        acc,i,base=[0]*(sct[-1]+1),0,0\n",
    "        for s in sct:\n",
    "            acc[base:s]=[i]*(s-base)\n",
    "            i+=ct[s]\n",
    "            acc[s]=i\n",
    "            base=s\n",
    "        rs=inf\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < sct[-1]: continue\n",
    "            b0,rs0=0,0\n",
    "            for b in box:\n",
    "                if b<b0:continue\n",
    "                if b>=sct[-1]:\n",
    "                    rs0+=b*(len(packages)-acc[b0])\n",
    "                    break\n",
    "                rs0+=b*(acc[b]-acc[b0])\n",
    "                b0=b\n",
    "            rs=min(rs0,rs)\n",
    "        return -1 if rs==inf else (rs-sum(packages))%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        ct=Counter(packages)\n",
    "        sct=list(ct)\n",
    "        sct.sort()\n",
    "        acc,i,base=[0]*(sct[-1]+1),0,0\n",
    "        for s in sct:\n",
    "            acc[base:s]=[i]*(s-base)\n",
    "            i+=ct[s]\n",
    "            acc[s]=i\n",
    "            base=s\n",
    "        rs=inf\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < sct[-1]: continue\n",
    "            b0,rs0=0,0\n",
    "            for b in box:\n",
    "                if b<b0:continue\n",
    "                if b>=sct[-1]:\n",
    "                    rs0+=b*(len(packages)-acc[b0])\n",
    "                    break\n",
    "                rs0+=b*(acc[b]-acc[b0])\n",
    "                b0=b\n",
    "                if rs0>=rs:break\n",
    "            rs=min(rs0,rs)\n",
    "        return -1 if rs==inf else (rs-sum(packages))%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        #packages.sort()\n",
    "        ct=Counter(packages)\n",
    "        sct=list(ct)\n",
    "        sct.sort()\n",
    "        acc=[0]*(sct[-1]+1)\n",
    "\n",
    "        i=0\n",
    "        base=0\n",
    "        for s in sct:\n",
    "            for j in range(base,s):\n",
    "                acc[j]=i\n",
    "            i+=ct[s]\n",
    "            acc[s]=i\n",
    "            base=s\n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "        rs=-1\n",
    "        rs0=0\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < sct[-1]: continue\n",
    "            while len(box)>1 and box[-2]>=sct[-1]:\n",
    "                box.pop()\n",
    "            while box[0]<sct[0]:\n",
    "                box.pop(0)   \n",
    "                \n",
    "            b0=0\n",
    "            rs0=0\n",
    "            for b in box:\n",
    "                if b>=sct[-1]:\n",
    "                    rs0+=b*(len(packages)-acc[b0])\n",
    "                    break\n",
    "                rs0+=b*(acc[b]-acc[b0])\n",
    "                b0=b\n",
    "            \n",
    "\n",
    "            rs=min(rs0,rs) if rs!=-1 else rs0\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        return -1 if rs==-1 else (rs-sum(packages))%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        \n",
    "        ct=Counter(packages)\n",
    "        sct=list(ct)\n",
    "        sct.sort()\n",
    "        acc=[0]*(sct[-1]+1)\n",
    "\n",
    "        i=0\n",
    "        base=0\n",
    "        for s in sct:\n",
    "            for j in range(base,s):\n",
    "                acc[j]=i\n",
    "            i+=ct[s]\n",
    "            acc[s]=i\n",
    "            base=s\n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "        rs=-1\n",
    "        rs0=0\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < sct[-1]: continue\n",
    "            while len(box)>1 and box[-2]>=sct[-1]:\n",
    "                box.pop()\n",
    "            while box[0]<sct[0]:\n",
    "                box.pop(0)   \n",
    "                \n",
    "            b0=0\n",
    "            rs0=0\n",
    "            for b in box:\n",
    "                if b>=sct[-1]:\n",
    "                    rs0+=b*(len(packages)-acc[b0])\n",
    "                    break\n",
    "                rs0+=b*(acc[b]-acc[b0])\n",
    "                b0=b\n",
    "            \n",
    "\n",
    "            rs=min(rs0,rs) if rs!=-1 else rs0\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        return -1 if rs==-1 else (rs-sum(packages))%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        ans = inf\n",
    "        ma = mapa = max(packages)\n",
    "        for box in boxes:\n",
    "            ma = max(ma,max(box))\n",
    "        \n",
    "        cnt = Counter(packages)\n",
    "        pre = [0] * (ma + 1)\n",
    "        su = [0] * (ma + 1)\n",
    "        for i in range(ma + 1):\n",
    "            pre[i] = pre[i - 1] + cnt[i]#到i要装几个货物\n",
    "            su[i] = su[i - 1] + cnt[i] * i#能装到i到货物重量前缀和\n",
    "        \n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            count = 0\n",
    "            \n",
    "            if box[-1] >= mapa:\n",
    "                for i in range(len(box)):\n",
    "                    if i == 0:\n",
    "                        count += pre[box[i]] * box[i] - su[box[i]]\n",
    "                    else:\n",
    "                        count += (pre[box[i]] - pre[box[i - 1]]) * box[i] - (su[box[i]] - su[box[i - 1]])\n",
    "                ans = min(ans, count)     \n",
    "        \n",
    "        if ans == inf:\n",
    "            return -1\n",
    "        \n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        P = [[0, 0] for i in range(10**5+1)]\n",
    "        packages = sorted(packages)\n",
    "        tempNum = 0\n",
    "        tempAllSize = 0\n",
    "        tempSize = packages[0]\n",
    "        for p in packages:\n",
    "            if p==tempSize:\n",
    "                tempNum += 1\n",
    "                tempAllSize += p\n",
    "            else:\n",
    "                P[tempSize] = [tempNum, tempAllSize]\n",
    "                for j in range(tempSize+1, p):\n",
    "                    P[j] =  [tempNum, tempAllSize]\n",
    "                tempSize = p\n",
    "                tempNum += 1\n",
    "                tempAllSize += p\n",
    "        P[tempSize] =  [tempNum, tempAllSize]\n",
    "        for j in range(tempSize + 1, 10**5+1):\n",
    "            P[j] = [tempNum, tempAllSize]\n",
    "\n",
    "        minWasted = float('inf')\n",
    "        for b in boxes:\n",
    "            tempWasted = 0\n",
    "            nums = 0\n",
    "            sizes = 0\n",
    "            for i in sorted(b):\n",
    "                tempWasted += i * (P[i][0]-nums) - (P[i][1]-sizes)\n",
    "                nums = P[i][0]\n",
    "                sizes = P[i][1]\n",
    "            if nums == len(packages):\n",
    "                if tempWasted < minWasted:\n",
    "                    minWasted = tempWasted\n",
    "        return minWasted%(10**9+7) if minWasted!=float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        ct=Counter(packages)\n",
    "        sct=list(set(packages))\n",
    "        sct.sort()\n",
    "        acc=[0]*(sct[-1]+1)\n",
    "        i=0\n",
    "        base=0\n",
    "        for s in sct:\n",
    "            acc[base:s]=[i]*(s-base)\n",
    "            i+=ct[s]\n",
    "            acc[s]=i\n",
    "            base=s\n",
    " \n",
    "        rs=inf\n",
    "        rs0=0\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < sct[-1]: continue\n",
    "            b0,rs0=0,0\n",
    "            for b in box:\n",
    "                if b<b0:continue\n",
    "                if b>=sct[-1]:\n",
    "                    rs0+=b*(len(packages)-acc[b0])\n",
    "                    break\n",
    "                rs0+=b*(acc[b]-acc[b0])\n",
    "                b0=b\n",
    "            rs=min(rs0,rs)\n",
    "        return -1 if rs==inf else (rs-sum(packages))%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        ct=Counter(packages)\n",
    "        sct=list(set(packages))\n",
    "        sct.sort()\n",
    "        acc=[0]*(sct[-1]+1)\n",
    "        i=0\n",
    "        base=0\n",
    "        for s in sct:\n",
    "            acc[base:s]=[i]*(s-base)\n",
    "            i+=ct[s]\n",
    "            acc[s]=i\n",
    "            base=s\n",
    " \n",
    "        rs=inf\n",
    "        rs0=0\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < sct[-1]: continue\n",
    "            b0,rs0=0,0\n",
    "            for b in box:\n",
    "                if b<b0:continue\n",
    "                if b>=sct[-1]:\n",
    "                    rs0+=b*(len(packages)-acc[b0])\n",
    "                    break\n",
    "                rs0+=b*(acc[b]-acc[b0])\n",
    "                b0=b\n",
    "            rs=min(rs0,rs)\n",
    "        return -1 if rs==inf else (rs-sum(packages))%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        \n",
    "        ct=Counter(packages)\n",
    "        sct=list(set(packages))\n",
    "        sct.sort()\n",
    "        acc=[0]*(sct[-1]+1)\n",
    "\n",
    "        i=0\n",
    "        base=0\n",
    "        for s in sct:\n",
    "            for j in range(base,s):\n",
    "                acc[j]=i\n",
    "            i+=ct[s]\n",
    "            acc[s]=i\n",
    "            base=s\n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "        rs=-1\n",
    "        rs0=0\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < sct[-1]: continue\n",
    "            while len(box)>1 and box[-2]>=sct[-1]:\n",
    "                box.pop()\n",
    "            while box[0]<sct[0]:\n",
    "                box.pop(0)   \n",
    "                \n",
    "            b0=0\n",
    "            rs0=0\n",
    "            for b in box:\n",
    "                if b>=sct[-1]:\n",
    "                    rs0+=b*(len(packages)-acc[b0])\n",
    "                    break\n",
    "                rs0+=b*(acc[b]-acc[b0])\n",
    "                b0=b\n",
    "            \n",
    "\n",
    "            rs=min(rs0,rs) if rs!=-1 else rs0\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        return -1 if rs==-1 else (rs-sum(packages))%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        counter = Counter(packages)\n",
    "        inc_packages = sorted(packages)\n",
    "        presum = [0]\n",
    "        for p in inc_packages:\n",
    "            presum.append(presum[-1] + p)\n",
    "        ans = float('inf')\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < inc_packages[-1]:\n",
    "                continue\n",
    "            wasted = 0\n",
    "            prev_idx = 0\n",
    "            for b in box:\n",
    "                first_larger_idx = bisect_right(inc_packages, b)\n",
    "                wasted += (first_larger_idx - prev_idx) * b - (presum[first_larger_idx] - presum[prev_idx])\n",
    "                prev_idx = first_larger_idx\n",
    "            ans = min(ans, wasted)\n",
    "        if ans == float('inf'):\n",
    "            return -1\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        packages=sorted(packages)\n",
    "        su=sum(packages)\n",
    "        r=packages[-1]\n",
    "        a={}\n",
    "        m=-1\n",
    "        for i in packages:\n",
    "            if i in a:\n",
    "                a[i]+=1\n",
    "            else:\n",
    "                a[i]=1\n",
    "        packages=sorted(list(set(packages)))\n",
    "        t=[0]\n",
    "        q=0\n",
    "        for i in range(r):\n",
    "            if i+1 in a:\n",
    "                q+=a[i+1]\n",
    "            t.append(q)\n",
    "        # print(t)\n",
    "        for i in range(len(boxes)):\n",
    "            lo=len(boxes[i])\n",
    "            boxes[i].sort()\n",
    "            if boxes[i][-1]<r:\n",
    "                continue\n",
    "            k=0\n",
    "            q=0\n",
    "            j=0\n",
    "            e=0\n",
    "            while j <len(boxes[i]):\n",
    "                if boxes[i][j]+1>=len(t):\n",
    "                    # print(q)\n",
    "                    q+=(t[-1]-t[e])*boxes[i][j]\n",
    "                    # print(q)\n",
    "                    break\n",
    "                else:\n",
    "                    q+=(t[boxes[i][j]]-t[e])*boxes[i][j]\n",
    "                    e=boxes[i][j]\n",
    "                j+=1\n",
    "                # print(q,e,j,(t[-1]-t[e])*boxes[i][j])\n",
    "            # print(q,m)\n",
    "            if m==-1:\n",
    "                m=q\n",
    "            else:\n",
    "                m=min(m,q)\n",
    "        if m==-1:\n",
    "            return -1\n",
    "        return (m-su)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from typing import List\n",
    "from collections import Counter, defaultdict, deque\n",
    "from functools import lru_cache\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        packages.sort()\n",
    "        # print(packages)\n",
    "        n = len(boxes)\n",
    "        lastPack = [-1] * n\n",
    "        cost = [0] * n\n",
    "\n",
    "        NP = len(packages)\n",
    "        acc = [0] * (NP+1)\n",
    "        for i in range(NP):\n",
    "            acc[i+1] = packages[i] + acc[i]\n",
    "\n",
    "\n",
    "        def searchMaxPack(size, s):\n",
    "            s = s + 1\n",
    "            e = len(packages) - 1\n",
    "            while s <= e:\n",
    "                m = (s + e) // 2\n",
    "                if packages[m] > size:\n",
    "                    e = m - 1\n",
    "                else:\n",
    "                    s = m + 1\n",
    "            return e\n",
    "\n",
    "        ev = []\n",
    "        for i in range(n):\n",
    "            for b in boxes[i]:\n",
    "                ev.append((b, i))\n",
    "        ev.sort()\n",
    "\n",
    "        for sz, idx in ev:\n",
    "            last = lastPack[idx]\n",
    "            if last == (NP-1): continue\n",
    "            now = searchMaxPack(sz, last)\n",
    "            accSize = acc[now + 1] - acc[last + 1]\n",
    "            # print(idx, sz, last, now, accSize)\n",
    "            cost[idx] += (now - last) * sz - accSize\n",
    "            lastPack[idx] = now\n",
    "\n",
    "        inf = 1 << 63\n",
    "        ans = inf\n",
    "        MOD = 10 ** 9 + 7\n",
    "        for i in range(n):\n",
    "            if lastPack[i] != (NP-1):\n",
    "                continue\n",
    "            ans = min(ans, cost[i])\n",
    "        if ans == inf:\n",
    "            return -1\n",
    "        return ans % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minWastedSpace(self, packages, boxes):\n",
    "        st = collections.Counter(packages)\n",
    "        total_packges = len(packages)\n",
    "        max_num = 10 ** 5 + 1\n",
    "        p = [0] * max_num\n",
    "        t = [0] * max_num\n",
    "        count = 0\n",
    "        base = 10 ** 9 + 7\n",
    "        for i in range(1, max_num):\n",
    "            p[i] = p[i - 1] + count\n",
    "            count += st[i]\n",
    "            t[i] = count\n",
    "        min_ans = float('inf')\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if t[box[-1]] < total_packges:\n",
    "                continue\n",
    "            total_ans = 0\n",
    "            for i in range(1, len(box)):\n",
    "                total_ans += t[box[i - 1]] * (box[i] - box[i - 1])\n",
    "            now_ans = p[box[-1]] - total_ans\n",
    "            min_ans = min(min_ans, now_ans)\n",
    "        if min_ans == float('inf'):\n",
    "            return -1\n",
    "        return min_ans % base"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        packages.sort(reverse=True)\n",
    "        boxes = [b for b in boxes if max(b)>=packages[0]]\n",
    "        if not boxes:\n",
    "            return -1\n",
    "        wastes = [[0,-1] for b in boxes]\n",
    "        prefix=[0]\n",
    "        for box,supplier_idx in sorted([b,i] for i,bxs in enumerate(boxes) for b in bxs):\n",
    "            while packages and packages[-1]<=box:\n",
    "                prefix.append(prefix[-1]+packages.pop())\n",
    "            w,i = wastes[supplier_idx]\n",
    "            j = len(prefix)-2\n",
    "            w2 = (j-i)*box-(prefix[j+1]-prefix[i+1])\n",
    "            wastes[supplier_idx] = [w2+w,j]\n",
    "        return min(wastes)[0] % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:\n",
    "        packages.sort()\n",
    "        ct=Counter(packages)\n",
    "        sct=list(ct)\n",
    "        sct.sort()\n",
    "        acc=defaultdict(int) #[0]*(sct[-1]+1)\n",
    "\n",
    "        i=0\n",
    "        base=0\n",
    "        for s in sct:\n",
    "            #for j in range(base,s):\n",
    "             #   acc[j]=i\n",
    "            i+=ct[s]\n",
    "            acc[s]=i\n",
    "            base=s\n",
    "            \n",
    "        #print(acc)\n",
    "        \n",
    "        accd=[0]*sct[0]\n",
    "        for i in range(0,len(sct)-1):\n",
    "            accd+=[acc[sct[i]]]*(sct[i+1]-sct[i])\n",
    "        \n",
    "        accd+=[acc[sct[-1]]]\n",
    "        #print(accd)\n",
    "        #return 0\n",
    "\n",
    "        rs=-1\n",
    "        rs0=0\n",
    "        for box in boxes:\n",
    "            box.sort()\n",
    "            if box[-1] < packages[-1]: continue\n",
    "            b0=0\n",
    "            rs0=0\n",
    "            for b in box:\n",
    "                if b>=packages[-1]:\n",
    "                    rs0+=b*(len(packages)-accd[b0])\n",
    "                    break\n",
    "                rs0+=b*(accd[b]-accd[b0])\n",
    "                b0=b\n",
    "            #print(rs0)\n",
    "\n",
    "            rs=min(rs0,rs) if rs!=-1 else rs0\n",
    "            #print(rs,sum(packages))\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        return -1 if rs==-1 else (rs-sum(packages))%1000000007"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
